package LibDL.data;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.IntStream;

import static java.util.Arrays.copyOfRange;

public class LibArrayInt {

    public int[] elementData;

    public int size;

    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final int[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */

    private static final int[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    public LibArrayInt(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new int[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                    initialCapacity);
        }
    }

    public LibArrayInt() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

    /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    public boolean add(int e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    /**
     * Returns the number of elements in this list.
     *
     * @return the number of elements in this list
     */
    public int size() {
        return size;
    }

    /**
     * Returns <tt>true</tt> if this list contains no elements.
     *
     * @return <tt>true</tt> if this list contains no elements
     */
    public boolean isEmpty() {
        return size == 0;
    }

//    TODO REMOVE
//    public List<Integer> argsort_boxed() {
//        List<Integer> sorted = new ArrayList<Integer>(this.size);
//        for (int i = 0; i < this.size; i++) {
//            sorted.add(i, i);
//        }
//        sorted.sort((o1, o2) -> elementData[o1] - elementData[o2]);
//        return sorted;
//    }

    public LibArrayInt(int[] elementData, int size) {
        this.elementData = elementData;
        this.size = size;
    }

    public LibArrayInt argsort() {
        int[] es = IntStream.range(0, this.size).toArray();
        LibArrayInt sorted = new LibArrayInt(es, this.size);
        sorted.sort(0, size, ((o1, o2) -> elementData[o1] - elementData[o2]));
        return sorted;
    }

    public void sort(int fromIndex, int toIndex) {
        sort(fromIndex, toIndex, ((x, y) -> x - y));
    }

    public void sort(int fromIndex, int toIndex, IntComparator c) {
        int[] aux = copyOfRange(this.elementData, fromIndex, toIndex);
        mergeSort(aux, this.elementData, fromIndex, toIndex, -fromIndex, c);
    }

    /**
     * Tuning parameter: list size at or below which insertion sort will be
     * used in preference to mergesort.
     * To be removed in a future release.
     */
    private static final int INSERTIONSORT_THRESHOLD = 7;
    /**
     * Src is the source array that starts at index 0
     * Dest is the (possibly larger) array destination with a possible offset
     * low is the index in dest to start sorting
     * high is the end index in dest to end sorting
     * off is the offset to generate corresponding low, high in src
     * To be removed in a future release.
     */
    private static void mergeSort(int[] src,
                                  int[] dest,
                                  int low,
                                  int high,
                                  int off,
                                  IntComparator c) {
        int length = high - low;

        // Insertion sort on smallest arrays
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i=low; i<high; i++)
                for (int j=i; j>low &&
                        c.compare(dest[j-1], dest[j]) >0 ; j--)
                    swap(dest, j, j-1);
            return;
        }

        // Recursively sort halves of dest into src
        int destLow  = low;
        int destHigh = high;
        low  += off;
        high += off;
        int mid = (low + high) >>> 1;
        mergeSort(dest, src, low, mid, -off, c);
        mergeSort(dest, src, mid, high, -off, c);

        // If list is already sorted, just copy from src to dest.  This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (c.compare(src[mid-1], src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // Merge sorted halves (now in src) into dest
        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && c.compare(src[p], src[q])<=0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

    /**
     * Swaps x[a] with x[b].
     */
    private static void swap(int[] x, int a, int b) {
        int t = x[a];
        x[a] = x[b];
        x[b] = t;
    }

    public LibArrayInt index_select(List<Integer> indices) {
        LibArrayInt out = new LibArrayInt(indices.size());
        for (Integer index : indices) {
            out.add(this.elementData[index]);
        }
        return out;
    }

    public LibArrayInt index_select(LibArrayInt indices) {
        LibArrayInt out = new LibArrayInt(indices.size());
        for (int i = 0; i < indices.size; i++) {
            out.add(elementData[indices.elementData[i]]);
        }
        return out;
    }

    public  LibArrayInt[] unique(boolean return_index, boolean return_inverse,boolean return_counts) {
        LibArrayInt unique, unique_indices, unique_inverse, unique_counts;
        LibArrayInt sorted = this.argsort();
        int tmp = 0;
        unique = new LibArrayInt(this.size());
        unique.add(this.elementData[sorted.get(0)]);
        unique_indices = new LibArrayInt(this.size());
        if(return_index) {
            unique_indices.add(sorted.get(0));
        }
        unique_inverse = new LibArrayInt(this.size());
        if(return_inverse) {
            for (int i = 0; i < this.size(); i++) {
                unique_inverse.add(-1);
            }
            unique_inverse.set(sorted.get(0), 0);
        }
        unique_counts = new LibArrayInt(this.size());
        if(return_counts) {
            unique_counts.add(1);
        }
        tmp++;
        while(tmp<sorted.size()) {
            if(this.elementData[sorted.get(tmp)] == (unique.get(unique.size()-1))){
                if(return_counts) {
                    unique_counts.set(unique.size() - 1, unique_counts.get(unique.size() - 1) + 1);
                }
                if(return_inverse) {
                    unique_inverse.set(sorted.get(tmp), unique.size() - 1);
                }
                if(return_index) {
                    if (sorted.get(tmp) < unique_indices.get(unique.size() - 1)) {
                        unique_indices.set(unique.size() - 1, sorted.get(tmp));
                    }
                }
            }else{
                unique.add(this.elementData[sorted.get(tmp)]);
                if(return_counts) {
                    unique_counts.add(1);
                }
                if(return_inverse) {
                    unique_inverse.set(sorted.get(tmp), unique.size() - 1);
                }
                if(return_index) {
                    unique_indices.add(sorted.get(tmp));
                }
            }
            tmp++;
        }
        unique.trimToSize();
        unique_indices.trimToSize();
        unique_inverse.trimToSize();
        unique_counts.trimToSize();
        if(return_index){
            if(return_inverse){
                if(return_counts){
                    return new LibArrayInt[]{unique,unique_indices,unique_inverse,unique_counts};
                }
                return new LibArrayInt[]{unique,unique_indices,unique_inverse};
            }
            if(return_counts){
                return new LibArrayInt[]{unique,unique_indices,unique_counts};
            }
            return new LibArrayInt[]{unique,unique_indices};
        }
        if(return_inverse){
            if(return_counts){
                return new LibArrayInt[]{unique,unique_inverse,unique_counts};
            }
            return new LibArrayInt[]{unique,unique_inverse};
        }
        if(return_counts){
            return new LibArrayInt[]{unique,unique_counts};
        }
        return new LibArrayInt[]{unique};
    }

    public void set(int index, int value) {
        elementData[index] = value;
    }

    public int get(int index) {
        return elementData[index];
    }

    public void trimToSize() {
        if (size < elementData.length) {
            elementData = Arrays.copyOf(elementData, size);
        }
    }

    public LibArrayInt subList(int fromIndex, int toIndex) { // TODO OPTI
        LibArrayInt sub = new LibArrayInt(0);
        sub.elementData = copyOfRange(this.elementData, fromIndex, toIndex);
        sub.size = sub.elementData.length;
        return sub;
    }

    public void arrAdd(int value) { // TODO OPTI
        for (int i = 0; i < size; i++) {
            this.elementData[i] = elementData[i] + value;
        }
    }

    public void addAll(LibArrayInt elements) { // TODO OPTI
        for (int i = 0; i < elements.size; i++) {
            this.add(elements.elementData[i]);
        }
    }
}

@FunctionalInterface
interface IntComparator{
    int compare(int x, int y);
}
